package sort;

public class MergeSort implements Sort {
    @Override
    public void sort(Comparable[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public void mergeSort(Comparable[] arr, int lo, int hi) {
        if (lo == hi) {
            return;
        } else {
            int mid = lo + ((hi - lo) >> 1);
            mergeSort(arr, lo, mid);
            mergeSort(arr, mid + 1, hi);
            merge(arr, lo, mid, hi);
        }

    }

    public void merge(Comparable[] arr, int lo, int mid, int hi) {
        Comparable[] helper = new Comparable[hi - lo + 1];
        int i = 0;
        int p1 = lo;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= hi) {
            helper[i++] = (SortCommon.less(arr[p1],arr[p2]) ? arr[p1++] : arr[p2++]);
        }
        if (p1 <= mid) {
            System.arraycopy(arr, p1, helper, i, mid - p1 + 1);
        } else if (p2 <= hi) {
            System.arraycopy(arr, p2, helper, i, hi - p2 + 1);
        }
        System.arraycopy(helper, 0, arr, lo, hi - lo + 1);
    }
}
